package 中等.二分查找;

import java.util.Arrays;

/**
 * 给你一个正整数数组 price ，其中 price[i] 表示第 i 类糖果的价格，另给你一个正整数 k 。
 * 商店组合 k 类 不同 糖果打包成礼盒出售。礼盒的 甜蜜度 是礼盒中任意两种糖果 价格 绝对差的最小值。
 * 返回礼盒的 最大 甜蜜度。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/maximum-tastiness-of-candy-basket
 */
public class 礼盒的最大甜蜜度_6271 {

    public static void main(String[] args) {

        //[13,5,1,8,21,2]
        //3
        System.out.println(maximumTastiness(new int[]{13, 5, 1, 8, 21, 2}, 3));

    }

    /**
     * 二分+贪心
     * 1，任意两种糖果价格绝对差的最小值，即价格排序后，相邻
     * 价格的差最小值，
     * 2，我们可以枚举答案最小值为 mid,
     * 然后判断是否可以从 price 数组中选取 k 个元素，使得
     * 他们排序后相邻价格查最小值 >=mid，如果能够满足
     * 条件，尽可能将 mid 增大，获取一个更大甜蜜度的答案，否则
     * 将 mid 减小来使得满足条件，可以用到二分查找
     * 3，判断是否可以从 price 数组中选取 k 个元素，先将其排序，首选选择
     * 最小价格，然后往后遍历，找到满足 diff<=mid 的第一个元素，
     * 如此找到 k 个元素
     * 4，二分单调性分析
     * 甜蜜度越大，越不容易满足选取k个元素，排序相邻差最小值 >=mid
     * 的条件，如果不满足，mid 越大也一定不满足，所有右边界收缩，降低
     * 甜蜜度范围
     */
    public static int maximumTastiness(int[] price, int k) {
        Arrays.sort(price);
        int minDiff = 0;
        int left = 0, right = price[price.length - 1] - price[0];

        while (left <= right) {
            int mid = left + (right - left) / 2;
            int preVal = price[0];
            int curK = 1;
            for (int i = 1; i < price.length && curK < k; i++) {
                if (price[i] - preVal >= mid) {
                    preVal = price[i];
                    curK++;
                }
            }

            if (curK == k) {
                minDiff = Math.max(minDiff, mid);
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return minDiff;
    }

}
